TabuSearchHeuristic::TabuSearchHeuristic( SubstractNetwork* sn, VirtualNetwork* vn ){

	this->vn = vn;
	this->sn = sn;
	
	vn_m = vn->getNumberOfNodes();
	vn_n = vn->getNumberOfEdges();
	
	sn_m = sn->getNumberOfNodes();
	sn_n = sn->getNumberOfEdges();
	
	vn_nodes = vn->getNodeList();
	sn_nodes = sn->getNodeList();
	
	current_solution.paths = NULL;
	current_solution.node_map = NULL;
	
	best_solution.paths = NULL;
	best_solution.node_map = NULL;
	
	choices = new int[vn_m];
	for( int i = 0; i < vn_m; ++i ){
		choices[i] = -1;
	}
	
	viable =  true;
	int i = sn_m-1;
	int j = vn_m-1;

	for( ; i >= 0 && j >= 0; ){
		if( vn_nodes[j].processing <= sn_nodes[i].processing ){
			if( i < j ) viable = false;
			choices[j] = i;
			j--;
		}else
			--i;
	}
	
	if( j >= 0 ){
		viable = false;
	}
	
	num_changes = 5;
	tenure = 10;
	iterations = 100;
}

void TabuSearchHeuristic::initialize(){
	
}

TabuSearchHeuristic::~TabuSearchHeuristic(){
	
	if( current_solution.paths ){
		for( int i = 0; i < vn_n; ++i )
			if( current_solution.paths[i] )
				delete current_solution.paths[i];
		delete [] current_solution.paths;
	}
	delete [] current_solution.node_map;
	
	if( best_solution.paths ){
		for( int i = 0; i < vn_n; ++i )
			if( best_solution.paths[i] )
				delete best_solution.paths[i];
		delete [] best_solution.paths;
	}
	delete [] best_solution.node_map;
	
	delete [] choices;
	
	
}

bool TabuSearchHeuristic::solve(){
	initialize();
	
	if( !viable ){
		return false;
	}
	
	getInitialSolution();
	
	best_solution.node_map = new struct Node*[vn_m];
	for( int i = 0; i < vn_m; ++i )
		best_solution.node_map[i] = NULL;
	best_solution.edges = 0;
	best_solution.paths = NULL;
	best_solution.viable = 0;
	
	for( int i = 0; i < vn_m; ++i )
		best_solution.node_map[i] = current_solution.node_map[i];
	best_solution.edges = current_solution.edges;
	best_solution.viable = current_solution.viable;
	best_solution.paths = new list<int>*[vn_n];
	for( int i = 0; i < vn_n; ++i ) 
		best_solution.paths[i] = NULL;
	for( int i = 0; i < vn_n; ++i )
		if( current_solution.paths[i] )
			best_solution.paths[i] = new list<int>(*current_solution.paths[i]);

		
	/*
	if( best_solution.viable )
		cout << "Custo inicial: " << best_solution.edges << endl;
	else
		cout << "Sem custo inicial: solucao inicial inviavel" << endl;
	//*/
	
	num_changes = 5;
	for( int i = 0; i < iterations; ++i ){
		struct solution neighborhood[num_changes*vn_m];
		//expandir vizinhos
		for( int j = 0, k = -1; j < num_changes*vn_m; ++j ){
			if( j % num_changes == 0 ) ++k;
			
			neighborhood[j].node_map = NULL;
			neighborhood[j].paths = NULL;
			
			calculateNeighborhood( &neighborhood[j], k );
			
		}
		//rankear vizinhos
		qsort( neighborhood, num_changes*vn_m, sizeof( struct solution ), compareSolutions );
		
		//escolher melhor vizinho não tabu
		//for( int k = 0; k < 0.25*num_changes*vn_m; ++k ){
		for( int k = 0; k < num_changes*vn_m; ++k ){
			if( neighborhood[k].viable ){
				current_solution.viable = 1;
				
				for( int i = 0; i < vn_m; ++i ){

					if( current_solution.node_map[i]->id != neighborhood[k].node_map[i]->id ){
						int index = 10000*i + 100*current_solution.node_map[i]->id + neighborhood[k].node_map[i]->id;
						if( TABU[index] == 0 ){
							
							if( neighborhood[k].node_map[i]->used ){
								//se chegar aqui o vizinho é viável mas há um nó virtual mapeado pra um nó físico 
								//que já é usado por outro nó da mesma rede virtual. entao segue para o proximo vizinho
								break;
							}
							else
								neighborhood[k].node_map[i]->used = true;
							
							current_solution.node_map[i]->used = false;
							
							TABU[index] = tenure;
							
							current_solution.node_map[i] = neighborhood[k].node_map[i];
							
							for( int j = 0; j < vn_n; ++j )
								(*current_solution.paths[j]) = (*neighborhood[k].paths[j]);
							
							current_solution.edges = neighborhood[k].edges;
							
							//se chegou aqui é porque escolheu um vizinho. então sai do laço
							goto done;
						}
					}
				}
			}
			else{
				break;
			}
		}
		
		done:
		
		//verificar se houve melhora
		if( current_solution.viable ){
			best_solution.viable = 1;
			if( current_solution.edges < best_solution.edges ){
				for( int i = 0; i < vn_m; ++i )
					best_solution.node_map[i] = current_solution.node_map[i];
				
				for( int j = 0; j < vn_n; ++j )
					(*best_solution.paths[j]) = (*current_solution.paths[j]);
					
				best_solution.edges = current_solution.edges;
			}
		}
		
		for( int j = 0; j < num_changes*vn_m; ++j ){
			delete [] neighborhood[j].node_map;
			if( neighborhood[j].paths )
				for( int k = 0; k < vn_n; ++k )
					if( neighborhood[j].paths[k] )
						delete neighborhood[j].paths[k];
			delete [] neighborhood[j].paths;
		}
		
		//atualizar lista tabu
		map<unsigned int, unsigned int>::iterator it = TABU.begin();
		while( it != TABU.end() ){
			--(it->second);
			if( it->second == 0 )
				TABU.erase(it);
			++it;
		}
		
	}
	
	if( best_solution.viable ){
		//cout << "Custo final: " << best_solution.edges << endl;
		return true;
	}
	else{
		//cout << "Sem custo final. Solucao inviavel" << endl;
		return false;
	}
}

void TabuSearchHeuristic::calculateNeighborhood( struct solution* s, int i ){
	
	s->node_map = new struct Node*[vn_m];
	s->edges = 0;
	s->viable = 1;
	
	for( int j = 0; j < vn_m; ++j )
		s->node_map[j] = current_solution.node_map[j];
	
	int k = rand()%(choices[i]+1);

	if( sn_nodes[k].used ){
		s->viable = 0;
		return;
	}
	
	s->node_map[i] = &sn_nodes[k];
	
	s->paths = new list<int>*[vn_n];
	for( int i = 0; i < vn_n; ++i )
		s->paths[i] = new list<int>;
			
	Edge*** vn_graph = vn->getGraph();
	Edge*** sn_graph = sn->getGraph();
	int e = 0;
	
	for( int i = 0; i < sn_m; ++i )
		for( int j = 0; j < sn_m; ++j )
			if( sn_graph[i][j] != NULL )
				sn_graph[i][j]->gama = 0;
	
	for( int i = 0; i < vn_m; ++i ){
		for( int j = i; j < vn_m; ++j ){
			if( vn_graph[i][j] != NULL ){
				int v1, v2;
				v1 = v2 = -1;
				for( int l = 0; l < vn_m; ++l ){
					if( vn_nodes[l].id == i )
						v1 = s->node_map[l]->id;
					else if( vn_nodes[l].id == j )
						v2 = s->node_map[l]->id;
				}
				if( v1 == -1 || v2 == -1 ){
					cerr << "Error in function greedyMethod: There is a allocated virtual node without correspent entrance in virtual graph." << endl;
					exit(-1);
				}

				int num_edges_on_path = buildPath( v1, v2, &s->paths[e], vn_graph[i][j]->bandwidth );
				if( num_edges_on_path > 0 ){
					s->edges += num_edges_on_path;
				}
				else{
					s->viable = 0;
					return;
				}
				if( s->paths[e]->front() != v1 || s->paths[e]->back() != v2 ){
					cerr << "Error in function calculateNeighborhood: The begin and end of path does not correspond to begin and end vertices." << endl;
					exit(-1);
				}
				
				//if the request is allocated, it updates gama values on the substract network
				if( s->paths[e] != NULL ){
					list<int>::iterator v1, v2;
					v1 = v2 = s->paths[e]->begin();
					++v2;
					while( v2 != s->paths[e]->end() ){
						if( sn_graph[*v1][*v2] != NULL ){
							sn_graph[*v1][*v2]->gama += vn_graph[i][j]->bandwidth;
							sn_graph[*v2][*v1]->gama += vn_graph[i][j]->bandwidth;
							++v2; ++v1;
						}
						else{
							cerr << "Error in function greedyMethod, while updating gama values: A invalid substract path was builded." << endl;
							exit(-1);
						}
					}
				}
				++e;
			}
		}
	}
	
}


void TabuSearchHeuristic::getInitialSolution(){
	
	for( int j = 0; j < sn_m; ++j )
		sn_nodes[j].used = false;
	
	current_solution.node_map = new struct Node*[vn_m];
	current_solution.edges = 0;
	current_solution.paths = NULL;
	current_solution.viable = 1;
	
	for( int i = 0; i < vn_m; ++i ){
		int k =  rand()%(choices[i]+1);
		while( sn_nodes[k].used )
			k =  rand()%(choices[i]+1);
		sn_nodes[k].used = true;
		
		current_solution.node_map[i] = &sn_nodes[k];
	}
	
	current_solution.paths = new list<int>*[vn_n];
	for( int i = 0; i < vn_n; ++i ) 
		current_solution.paths[i] = new list<int>;
		
	Edge*** vn_graph = vn->getGraph();
	Edge*** sn_graph = sn->getGraph();
	int e = 0;
	
	for( int i = 0; i < sn_m; ++i )
		for( int j = 0; j < sn_m; ++j )
			if( sn_graph[i][j] != NULL )
				sn_graph[i][j]->gama = 0;
			
	for( int i = 0; i < vn_m; ++i ){
		for( int j = i; j < vn_m; ++j ){
			if( vn_graph[i][j] != NULL ){
				int v1, v2;
				v1 = v2 = -1;
				for( int k = 0; k < vn_m; ++k ){
					if( vn_nodes[k].id == i )
						v1 = current_solution.node_map[k]->id;
					else if( vn_nodes[k].id == j )
						v2 = current_solution.node_map[k]->id;
				}
				if( v1 == -1 || v2 == -1 ){
					cerr << "Error in function greedyMethod: There is a allocated virtual node without correspent entrance in virtual graph." << endl;
					exit(-1);
				}
				
				int num_edges_on_path = buildPath( v1, v2, &current_solution.paths[e], vn_graph[i][j]->bandwidth );
				if( num_edges_on_path > 0 ){
					current_solution.edges += num_edges_on_path;
				}
				else{
					current_solution.viable = 0;
					return;
				}
				if( current_solution.paths[e]->front() != v1 || current_solution.paths[e]->back() != v2 ){
					cerr << "Error in function getInitialSolution: The begin and end of path does not correspond to begin and end vertices." << endl;
					exit(-1);
				}
				//if the request is allocated, it updates gama values on the substract network
				if( current_solution.paths[e] != NULL ){
					list<int>::iterator v1, v2;
					v1 = v2 = current_solution.paths[e]->begin();
					++v2;
					while( v2 != current_solution.paths[e]->end() ){
						if( sn_graph[*v1][*v2] != NULL ){
							sn_graph[*v1][*v2]->gama += vn_graph[i][j]->bandwidth;
							sn_graph[*v2][*v1]->gama += vn_graph[i][j]->bandwidth;
							++v2; ++v1;
						}
						else{
							cerr << "Error in function greedyMethod, while updating gama values: A invalid substract path was builded." << endl;
							exit(-1);
						}
					}
				}
				
				++e;
			}
		}
	}
}

int TabuSearchHeuristic::buildPath( int v1, int v2, list<int>** path, int min_bw ){
	int num_edges_on_path = 0;
	
	Edge*** sn_graph = sn->getGraph();
	
	vector<struct V> Q(sn_m);
	for( int i = 0; i < sn_m; ++i ){
		Q[i].d = INT_MAX;
		Q[i].pi = -1;
	}
	Q[v1].d = 0;
	list<int> A;
	
	int sizeQ = sn_m;
	while( sizeQ > 0 ){
		int min = INT_MAX;
		int u;
		for( int i = 0; i < sn_m; ++i ){
			if( min > Q[i].d && Q[i].d != -1 ){
				min = Q[i].d;
				u = i;
			}
		}
		Q[u].d = -1;
		--sizeQ;
		
		A.push_back( u );
		for( int v = 0; v < sn_m; ++v ){
			if( sn_graph[u][v] != NULL && Q[v].d != -1 && sn_graph[u][v]->bandwidth-sn_graph[u][v]->gama >= min_bw ){
				if( Q[v].d > Q[u].d + 1 ){
					Q[v].d = Q[u].d + 1;
					Q[v].pi = u;
				}
			}
		}
	}
	
	if( Q[v2].pi == -1 ){
		return num_edges_on_path;
	}
	
	(*path)->push_front( v2 );

	struct V it = Q[v2];
	while( it.pi != v1 ){
		if( it.pi == -1 ){
			cerr << "Error in function buildPath: path builded breaks bandwidth constraint." << endl;
			exit(-1);
		}
		(*path)->push_front( it.pi );
		++num_edges_on_path;
		it = Q[it.pi];
	}
	++num_edges_on_path;
	(*path)->push_front( v1 );
	
	return num_edges_on_path;
}


void TabuSearchHeuristic::copySolution( struct Node* vnodes, Edge*** graph ){
	for( int i = 0; i < vn_m; ++i ){
		vnodes[i].target_node = best_solution.node_map[i]->id;
	}
	
	int e = 0;
	for( int i = 0; i < vn_m; ++i ){
		for( int j = i; j < vn_m; ++j ){
			if( graph[i][j] != NULL ){
				graph[i][j]->sn_path = new list<int>( *best_solution.paths[e] );
				++e;
			}
		}
	}
	
}